package leetcode.backtrace;

import leetcode.backtrace.common.BackTraceUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class backtrace01 {
    public static void main(String[] args) {
        int totalPrice = 35;
        System.out.println("目标置换物品的价值：" + totalPrice);
        int[] priceList = {1, 2, 5, 7, 9, 10, 15, 20};
        System.out.println("已获得物品价值依次是：" + Arrays.toString(priceList));
        System.out.println("依次拿取物品序号的方案有：");
        exchange(totalPrice, priceList);

        System.out.println("======================");
        int curIndex = 0;
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> curResult = new ArrayList<>();
        solveProblem(totalPrice, priceList, result, curResult, curIndex);
        System.out.println("依次拿取物品序号的方案有：" + result);
    }

    private static void solveProblem(int totalPrice, int[] priceList, List<List<Integer>> result, List<Integer> curResult, int curIndex) {
        if (BackTraceUtils.listToSum(curResult) == totalPrice) {
            result.add(new ArrayList<>(curResult));
        }
        // 遍历所有的兄弟节点
        for (int i = curIndex; i < priceList.length; i++) {
            // 检查选项
            if (BackTraceUtils.listToSum(curResult) + priceList[i] > totalPrice) {
                continue;
            }
            // 做选择
            curResult.add(priceList[i]);
            // 进入下一轮选择,相当于进入了树的下一层
            solveProblem(totalPrice, priceList, result, curResult, i + 1);
            // 撤销选择,相当于回到上一层
            curResult.remove(curResult.size() - 1);
        }
    }

    private static void exchange(int t, int[] priceList) {
        int n = priceList.length;
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        int num = 0;
        while (i < n || !stack.isEmpty()) {
            while (t > 0 && i < n) {
                // 一直在往下做选择
                if (t >= priceList[i]) {
                    // 选择当前商品
                    stack.push(i);
                    t = t - priceList[i];
                }
                // 进入下一个商品
                i++;
                if (t == 0) {
                    System.out.print("取序号为 " + stack + " 的物品, ");

                    List<Integer> curList = new ArrayList<>();
                    for (int j = 0; j < stack.size(); j++) {
                        curList.add(priceList[stack.get(j)]);
                    }
                    System.out.println("价值为 ==> " + curList);

                    num++;
                }
            }
            // 撤销最近的一次选择
            i = stack.pop();
            t = t + priceList[i];
            // 跳到兄弟节点
            i++;
        }
        if (num == 0) {
            System.out.println("无方案");
        }
    }

}
